import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        System.out.println();
    }

    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode Convert(TreeNode root){
        if(root == null) return null;

        //用中序遍历将节点传入链表
        ArrayList<TreeNode> list = new ArrayList<>();
        inOrder(root,list);

        //确定每个节点的前后
        int size = list.size();
        for (int i = 1; i < size - 1; i++) {
            TreeNode cur = list.get(i);
            cur.left = list.get(i - 1);
            cur.right = list.get(i + 1);
        }

        //解决头尾两节点
        if(size > 1){
            list.get(0).right = list.get(1);
            list.get(size - 1).left = list.get(size - 2);
        }
        return list.get(0);
    }

    private void inOrder(TreeNode root, ArrayList<TreeNode> list) {
        if(root == null) return;
        inOrder(root.left,list);
        list.add(root);
        inOrder(root,list);
    }

}
